package com.jojo.elementary.day14_tree;

import com.jojo.elementary.entity.TreeNode;

import java.util.*;

/**
 * 653. 两数之和 IV - 输入二叉搜索树
 *
 * 给定一个二叉搜索树 root 和一个目标结果 k，如果二叉搜索树中存在两个元素且它们的和等于给定的目标结果，则返回 true。
 *
 * 示例 1：
 * 输入: root = [5,3,6,2,4,null,7], k = 9
 * 输出: true
 *
 * 示例 2：
 * 输入: root = [5,3,6,2,4,null,7], k = 28
 * 输出: false
 */
public class TwoNumSum4 {

    /** myCode Hash表加中序遍历 */
    public boolean findTarget(TreeNode root, int k) {
        Set<Integer> set = new HashSet<>();
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null){
            if (root != null){
                stack.push(root);
                root = root.left;
            }else {
                TreeNode pop = stack.pop();
                if(set.contains(k - pop.val)){
                    return true;
                }else {
                    set.add(pop.val);
                }
                root = pop.right;
            }
        }
        return false;
    }
}
